This invention relates to set-associative memories.
One conventional form of set-associative memory comprises a plurality of random access memories (RAMs), each RAM location holding a data item and a tag value identifying the data. An input address is hashed (i.e. transformed by a many-to-one mapping function) to produce a hash address, which is applied in parallel to all the RAMs, so as to select one location in each RAM. The tag values in the addressed locations are then examined to see if the desired data is resident in one of them and, if so, the data is accessed.
If there are n RAMs, so that n locations at a time are examined, the memory is referred to as an n-way set-associative memory and is said to have an associativity of n. The usual choice for the value of n is 2 or 4.
Such a set-associative memory may be used, for example, as a cache memory for a computer system. The aim of a cache is to keep the most useful data of a large amount of data in a small, fast memory in order to avoid having to retrieve the data from the larger, slower main memory. If the required data is in the cache, it is said that a "hit" has occurred; otherwise a "miss" has occurred. The percentage of misses is called the "miss rate". A common engineering problem in designing a cache is to minimize the miss rate while keeping the cache size, the access speed, the power consumption and the amount of implementation logic fixed.
In general, the miss rate of such a cache decreases as its set associativity increases. On the other hand, the cost of implementation increases as set associativity increases. Thus, in general, known caches that deliver minimum miss rates demand large amounts of logic and space to implement, while known caches that are the cheapest to implement deliver higher miss rates.
Another use of set-associative memory is to form a content addressable memory (CAM). The aim of a CAM is to store and reference data according to its contents. For instance, performing a join of two relations within a relational database query can be implemented by first storing the contents of one relation in the CAM, indexed by the join attribute, and then secondly by comparing the rows of the second relation to the CAM using the join attribute again. Content addressable memories can be implemented by fully associative memories but their size is limited by the space demanded by fully associative logic.
One object of the present invention is to provide an improved set-associative memory which is capable of performing as well as conventional set-associative memories of higher set associativity, or better than conventional set-associative memories of the same set associativity. For example, when the set-associative memory is used as a cache, this means that it is able to deliver the same miss rate as conventional caches of larger size and cost, or lower miss rates than conventional caches of the same size and cost.
A second object of the present invention is to provide a CAM using a modified set-associative memory. This allows both much larger CAMs to be constructed and an improved read performance over present CAMs.